#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool searchMatrix(vector<vector<int> > &matrix, int target) {
	// Start typing your C/C++ solution below
	// DO NOT write int main() function

	if(target < matrix[0][0] || target > matrix[matrix.size()-1][matrix[0].size()-1])
		return false;
	
	// row binary search
	int left = 0;
	int right = matrix.size();
	while(left < right-1){
		int mid = (left+right)/2;
		if(target == matrix[mid][0])
			return true;
		else if(target < matrix[mid][0]){
			right = mid;
		}
		else{
			left = mid;
		}
	}
	// left point to the possible one
	vector<int>::iterator it = find(matrix[left].begin(), matrix[left].end(), target);
	if(it == matrix[left].end())
		return false;
	return true;
}


int main(){
	vector<vector<int> > out;
	vector<int> in;
	in.push_back(1);
	in.push_back(3);
	out.push_back(in);

	cout<<searchMatrix(out, 3);
	return 0;
}